package com.leetcode.动态规划;

/**
 * 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
 * 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
 *
 */
public class L516最长回文子序列 {
	public static void main(String[] args) {
		int result = longestPalindromeSubseq("cbbd");
		System.out.println(result);
	}
	/**
	 * dp[i][j]:以i位置为开始，j位置为结尾的范围内最长回文子串的长度为dp[i][j]，根据定义,i <= j，dp[i][j]才有意义
	 * 
	 */
	public static int longestPalindromeSubseq(String s) {
		int[][] dp = new int[s.length()][s.length()];
		for(int i = s.length() - 1;i >= 0;i--) {
			for(int j = i;j < s.length();j++) {
				//三种情况：
				if(i == j)
					dp[i][j] = 1;//只有一个字符，是回文串，且长度是1
				else if(i == j - 1)
					dp[i][j] = s.charAt(i) == s.charAt(j) ? 2 : 1;//如果是相邻，最少的回文串长度也是1
				else {//i、j的其他情况需要再次进行判断：
					if(s.charAt(i) == s.charAt(j))
						dp[i][j] = dp[i + 1][j - 1] + 2;
					else
						dp[i][j] = Math.max(dp[i][j - 1],dp[i + 1][j]);
				}
			}
		}
		return dp[0][s.length() - 1];
    }
}
